# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 10/50 获取生成数组中的最大值
# leetcode第1043题: https://leetcode.cn/problems/partition-array-for-maximum-sum/description/

def maxSumAfterPartitioning_wrong(arr: list[int], k: int) -> int:
    """一个错误的想法: 本质上使用的是贪心的算法
    一刀切地在子数组中使用最大的元素填满就一定可以获得全局的最大值"""
    n = len(arr)
    if n < 2:
        return arr[0]
    dp = [0] * (n + k - 1)
    dp[0] = arr[0]
    m = arr[0]  # m表示在i前的k个数中出现的最大的数字, 初始值为arr[0]
    for i in range(1, n + k - 1):
        if i < k:  # 当i小于k时, 当前值即为最大值与当前遍历数量的乘积
            m = max(m, arr[i])
            dp[i] = m * (i + 1)
        elif k <= i < n:  # 当i大于等于k时, 则需要考虑k个元素前的值
            m = max(arr[i - k + 1:i + 1])  # m表示在i前的k个数中出现的最大的数字
            dp[i] = max(dp[i - k] + m * k, dp[i - 1] + arr[i])
        else:  # 如果最后k位中包含多个较大值, 则需要考虑超出部分的情况, 见arr1
            m = max(arr[i - (n + k - 1):])  # m表示最后k位(包括了后面的0位)里面的最大值
            dp[i] = max(dp[i - k] + m * k, dp[i - 1]) + m * (n - i - 1)
    return max(dp[n - 1:n + k])


def maxSumAfterPartitioning_dfs(arr: list[int], k: int) -> int:
    """动态规划问题都可以转换为一个使用暴力递归的方法来求解, 本质上就是使用一个dfs算法来遍历所有可能性.
    在本题中, 使用dfs算法的递归将考虑所有可能的分隔数组的组合方式, 即可以使用dfs遍历一个k叉树的方式来查找所有可能.
    问题是, 在K比较大或者arr的大小比较大的时候就会耗时过长, 所以考虑添加一个mapping来对已经计算过的结果进行映射.
    """
    n = len(arr)
    mapping = {}

    def dfs(arr: list[int], start, k: int):
        cur_max, res = 0, 0
        if start > n:
            return 0
        if mapping.get(start) is not None:
            return mapping.get(start)

        for i in range(start, min(start + k, n)):
            cur_max = max(cur_max, arr[i])
            length = i - start + 1
            res = max(res, cur_max * length + dfs(arr, i + 1, k))

        mapping[start] = res
        return res

    return dfs(arr, 0, k)


def maxSumAfterPartitioning(arr: list[int], k: int) -> int:
    """动态规划方法
    以 arr = [1, 15, 7, 9, 2, 5, 10] k=3 为例
    dp[0] = 0
    dp[1] = 1
    dp[2] = max(dp[1] + 15 * 1, dp[0] + 15 * 2) = 30
    dp[3] = max(dp[2] + 7 * 1, dp[1] + 15 * 2, dp[0] + 15 * 3) = 45
    """
    n = len(arr)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        max_v = arr[i - 1]
        for j in range(i - 1, max(-1, i - k - 1), -1):
            dp[i] = max(dp[i], dp[j] + max_v * (i - j))
            if j > 0:
                max_v = max(max_v, arr[j - 1])
    return dp[n]


if __name__ == '__main__':
    arr = [1, 15, 7, 9, 2, 5, 10]
    print(maxSumAfterPartitioning(arr, 3))  # 84 [15,15,15,9,10,10,10]
    # 1, 15, 7,  9,       2,        5,        10,       0         0
    # 1, 30, 45, 45+9=54, 30+27=57, 45+27=72, 54+30=84, 57+20=77, 72+10=82
    arr1 = [1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3]
    print(maxSumAfterPartitioning(arr1, 4))  # 83 [1,7,7,7,7,9,9,9,9,9,9] 1 + 28 + 54
    # 1, 4, 1,  5,  7,       3,       6,        1,        9,        9,        3,        0         0         0
    # 1, 8, 12, 20, 1+28=29, 8+28=36, 12+28=40, 20+28=48, 29+36=65, 36+36=72, 40+36=76, 48+27=75, 65+18=83, 72+9=81
    arr2 = [4, 7, 5]
    # 4, 7,  5                   0
    # 4, 14, max(5+14, 14+4)=19  max(14+5)
    print(maxSumAfterPartitioning(arr2, 2))  # 19
    arr3 = [10, 4, 6, 4]
    # 10, 4,  6,  4,             0   0
    # 10, 20, 30, max(34,28)=34, 32,
    print(maxSumAfterPartitioning(arr3, 3))  # 34
    arr4 = [581920, 200100, 526972, 677934, 989025, 294832, 581857, 663919, 961334, 1881, 859626, 251114, 361905,
            867006,
            86001, 836946, 894279, 859796, 750025, 898166, 674980, 939280, 458563, 117387, 403337, 961067, 589597,
            73584,
            178968, 955900, 755634, 609754, 97612, 19699, 843950, 907919, 883083, 522938, 670930, 671679, 390248,
            704834,
            188158, 226340, 80496, 701795, 867627, 280988, 465918, 748627, 321025, 564279, 79716, 786173]
    print(len(arr4))
    print(maxSumAfterPartitioning(arr4, 23))  # 52072023
